As movement continues to an increasingly online world, the use of public-key cryptography will be prevalent. Underlying such use, a public-key infrastructure that constitutes the policy, procedures, personnel, and facilities for binding public keys to authorizations must be established. The public-key infrastructure is managed by a certificate authority (CA) who not only issues digital certificates that bind public keys to identities or authorizations, but also who manages these digital certificates. When issuing a certificate, the certificate authority must be sure to check that a user's credentials are accurate. However, if a certificate needs to be revoked, procedures may get more complex.
While a certificate's validity may be limited by an expiration date, there are instances when a certificate must be revoked prior to its expiration date. For example, a key holder may change his affiliation or position, or even worse his private key may have been compromised. Accordingly, some mechanism is needed for revoking a certificate.
One common approach for revoking a certificate is through the use of a certificate revocation list (CRL) that is a digitally signed and time-stamped list issued by the certificate authority specifying which certificates have been revoked according to some identifier like a serial number, a name, an e-mail address, etc. These CRLs must be distributed periodically, even if there are no changes, to prevent any type of replay attack. While this approach may appear simple, the management of CRLs may be unwieldy with respect to communication, search, and verification costs.
An alternate approach is through the use of a Certificate Revocation Tree (CRT). A CRT is a Merkle tree in which each leaf is associated with groups of revoked certificates. One can then form logical proofs using the leaf elements, and these proofs can be validated through properties of Merkle Trees.
Rather than posting full-fledged lists of revoked certificates, the certificate authority may instead choose to answer queries about specific certificates using an on-line approach. This approach is used in Online Certificate Status Protocol (OCSP). However, this approach has limitations. To begin with, the validity proof consists of a digital signature that may be quite long; for example, with RSA signatures, and a 1024-bit key, the signatures would be 1024-bits long. Moreover, 1024-bit keys are on the low end with respect to security. For any more long-term needs, a key along the lines of 2048-bits would have to be considered. Since the certificate authority must be very secure, its signing key will be correspondingly longer. Thus, a key size of 2048-bits for RSA is not unreasonable. In addition, signing each response may be computationally infeasible for the certificate authority who may have to handle numerous requests. If the certificate authority is a single centralized machine, then that causes a major scalability issue because all requests are routed through it, and it has to compute a digital signature for each unique request. By trying to introduce some load balancing and distributing the certificate authority, a security risk is introduced, as the sensitive signing key will be replicated.
Micali addressed these problems in an elegant scheme referred to as NOVOMODO. The NOVOMODO scheme works with any standard certificate format such as X.509 and allows a certificate authority to provide validity status of a certificate at any pre-specified time interval such as a day, an hour, etc. NOVOMODO uses a hash chain together with a single digital signature. The advantage is the cost of the single signature is amortized over many validity proofs. However, NOVOMODO requires traversal on the hash chains with time proportional to the number of periods that have passed between two queries. A natural extension pointed out by Naor and Nissim is to use Merkle trees (M. Naor and K. Nissim, “Certificate Revocation and Certificate Update,” Proceedings of USENIX Security, 1998). In this approach, the verifier has to compute ┌ log2 (365)┐+1 hashes to validate a certificate, though the validity proof now consists of ┌ log2 (365)┐+1 hash values. On average, this approach is desirable compared to the original NOVOMODO approach since the average verification complexity has gone down substantially. However, there are still some disadvantages:                1. If the time between verifications is smaller than ┌ log2 (365)┐+1, then the original NOVOMODO scheme requires less time for the verifier to validate the certificate.        2. The proof size in the original NOVOMODO scheme is always 1 hash value, which is much smaller than the proof size of the extended NOVOMODO scheme.For more information on NOVOMODO, see S Micali, “NOVOMODO: Scalable Certificate Validation and Simplified PKI Management, Proceedings of the 1st Annual PKI Research Workshop, 2002.        
Another approach referred to herein as the ALO approach, is due to Aiello, Lodha, and Ostrovsky and uses a NOVOMODO-like scheme in conjunction with a mechanism for partitioning users into subsets in order to provide validation proofs for multiple users simultaneously. See W. Aiello, S. Lodha and R. Ostrovsky, “Fast Digital Identity Revocation,” Proceedings of Asiacrypt '01, 2001.
The ALO scheme assigns a separate NOVOMODO-like hash chain to each such user subset Si. Then, at a given interval, if T denotes the set of users with revoked certificates, then the certificate authority first computes the covering indices i1 . . . , ik with T=∪j=1kSij. It then provides validity proofs for each subset Sij. This allows groups of users to be validated simultaneously. There are some drawbacks to this approach. First, there is additional overhead with respect to constructing subsets and having chains for each subset. At a bare minimum, the singleton subsets have to be created (which basically yields the original NOVOMODO scheme). Therefore, if one were to actually get an improvement through the ALO scheme, one would need to compute additional subsets, which means that additional work is required. Second, as in the original NOVOMODO scheme, the number of hash computations is proportional to the interval between validation checks; so might be large.